package leetcode.code1600;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class ThroneInheritance {

	String king;
	Map<String, List<String>> children;
	Map<String, Integer> adds;
	Map<String, String> father;
	Set<String> dead;

	public ThroneInheritance(String kingName) {
		king = kingName;
		dead = new HashSet<>();
		children = new HashMap<>();
		father = new HashMap<>();
	}

	private void successor(String x, List<String> curOrder) {
		if (!children.containsKey(x) || adds.getOrDefault(x, 0) == children.get(x).size()) {
			if (!x.equals(king)) {
				this.successor(father.get(x), curOrder);
			}
		} else {
			int index = adds.getOrDefault(x, 0);
			String child = children.get(x).get(index);
			if (!dead.contains(child)) {
				curOrder.add(child);
			}
			adds.put(x, index + 1);
			this.successor(child, curOrder);
		}
	}

	public void birth(String parentName, String childName) {
		children.computeIfAbsent(parentName, key -> new ArrayList<>()).add(childName);
		father.put(childName, parentName);
	}

	public void death(String name) {
		dead.add(name);
	}

	public List<String> getInheritanceOrder() {
		adds = new HashMap<>();
		List<String> curOrder = new ArrayList<>();
		if(!dead.contains(king)) {
			curOrder.add(king);
		}
		this.successor(king, curOrder);
		return curOrder;
	}
	
	public static void main(String[] args) {
		ThroneInheritance t= new ThroneInheritance("king"); // 继承顺序：king
		t.birth("king", "andy"); // 继承顺序：king > andy
		t.birth("king", "bob"); // 继承顺序：king > andy > bob
		t.birth("king", "catherine"); // 继承顺序：king > andy > bob > catherine
		t.birth("andy", "matthew"); // 继承顺序：king > andy > matthew > bob > catherine
		t.birth("bob", "alex"); // 继承顺序：king > andy > matthew > bob > alex > catherine
		t.birth("bob", "asha"); // 继承顺序：king > andy > matthew > bob > alex > asha > catherine
		t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
		t.death("bob"); // 继承顺序：king > andy > matthew > bob（已经去世）> alex > asha > catherine
		t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "alex", "asha", "catherine"]

	}

}
